﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    /*
     * 二叉树的最大深度
     * 
     */
    public class _104MaximumDepthOfBinaryTree
    {
        public int MaxDepth1(TreeNode root)
        {
            if (root == null)
                return 0;

            Queue<TreeNode> _Queue = new Queue<TreeNode>();
            _Queue.Enqueue(root);

            int _LeveSize = 1;
            int _Depth = 0;
            TreeNode _Temp;

            while (_Queue.Count != 0)
            {
                _Temp = _Queue.Dequeue();
                _LeveSize--;

                if (_Temp.left != null)
                    _Queue.Enqueue(_Temp.left);

                if (_Temp.right != null)
                    _Queue.Enqueue(_Temp.right);

                if (_LeveSize == 0)
                {
                    _Depth++;
                    _LeveSize = _Queue.Count;
                }
            }
            return _Depth;
        }

        public int MaxDepth(TreeNode root)
        {
            if (root == null)
                return 0;
            else
            {
                int left = MaxDepth(root.left);
                int right = MaxDepth(root.right);

                return Math.Max(left, right) + 1;
            }

        }
    }


    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }
}
